﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Problem15
{
    class Program
    {
        static void Main(string[] args)
        {
            List<List<long>> grid = new List<List<long>>(21);
            for (int i = 0; i <= 20; i++)
            {
                grid.Add(new List<long>(21));

                for (int j = 0; j <= 20; j++)
                {
                    grid[i].Add(-1);
                }
            }

            grid[20][20] = 1;

            long latticePathes = GetNumOfLatticePaths(0, 0, grid);

            Console.WriteLine(latticePathes);
            Console.ReadKey();
        }

        private static long GetNumOfLatticePaths(int i, int j, List<List<long>> grid)
        {
            if (i > 20 || j > 20) return 0; 

            if (grid[i][j] != -1) return grid[i][j];

            return grid[i][j] = GetNumOfLatticePaths(i + 1, j, grid) + GetNumOfLatticePaths(i, j + 1, grid);
        }
    }
}
